|
In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph ''G'', find the maximal number of edges in an ''n''-vertex graph which does not have a subgraph isomorphic to ''G''. In this context, ''G'' is called a forbidden subgraph.〔''Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Probabilistic Combinatorics'', Béla Bollobás, 1986, ISBN 0-521-33703-8, (p. 53, 54 )〕 It is also called the Turán-type problem and the corresponding number is called the Turán number for graph ''G''. It is called so in memory of Pál Turán, who determined this number for all ''n'' and all complete graphs .〔(p. 254 )〕 An equivalent problem is how many edges in an ''n''-vertex graph guarantee that it has a subgraph isomorphic to ''G''?〔"Modern Graph Theory", by Béla Bollobás, 1998, ISBN 0-387-98488-7, (p. 103 )〕 The problem may be generalized for a set of forbidden subgraphs ''S'': find the maximal number of edges in an ''n''-vertex graph which does not have a subgraph isomorphic to any graph form ''S''.〔Handbook of Discrete and Combinatorial Mathematics By Kenneth H. Rosen, John G. Michaels (p. 590 )〕 ==See also== *Biclique-free graph *Erdős–Hajnal conjecture *Turán number *Subgraph isomorphism problem *Forbidden graph characterization *Zarankiewicz problem 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Forbidden subgraph problem」の詳細全文を読む スポンサード リンク
|